1. Field of the Invention
This invention relates to coding methods and apparatuses, and more particularly to a method and apparatus for concatenated channel coding in a data communication system.
2. Description of Related Art
As described in the commonly assigned related co-pending application Ser. No. 08/974,376, a wireless communication system facilitates two-way communication between a plurality of subscriber radio stations or subscriber units (fixed and portable) and a fixed network infrastructure. Exemplary communication systems include mobile cellular telephone systems, personal communication systems (PCS), and cordless telephones. The key objective of these wireless communication systems is to provide communication channels on demand between the plurality of subscriber units and their respective base stations in order to connect a subscriber unit user with the fixed network infrastructure (usually a wire-line system). In the wireless systems having multiple access schemes a time xe2x80x9cframexe2x80x9d is used as the basic information transmission unit. Each frame is sub-divided into a plurality of time slots. Some time slots are used for control purposes and some for information transfer. Subscriber units typically communicate with a selected base station using a xe2x80x9cduplexingxe2x80x9d scheme thus allowing for the exchange of information in both directions of connection.
Transmissions from the base station to the subscriber unit are commonly referred to as xe2x80x9cdownlinkxe2x80x9d transmissions. Transmissions from the subscriber unit to the base station are commonly referred to as xe2x80x9cuplinkxe2x80x9d transmissions. Depending upon the design criteria of a given system, the prior art wireless communication systems have typically used either time division duplexing (TDD) or frequency division duplexing (FDD) methods to facilitate the exchange of information between the base station and the subscriber units. Both the TDD and FDD duplexing schemes are well known in the art.
Recently, wideband or xe2x80x9cbroadbandxe2x80x9d wireless communications networks have been proposed for delivery of enhanced broadband services such as voice, data and video. The broadband wireless communication system facilitates two-way communication between a plurality of base stations and a plurality of fixed subscriber stations or Customer Premises Equipment (CPE). One exemplary broadband wireless communication system is described in the co-pending application Ser. No. 08/974,376 which now is a U.S. Pat. No. 6,016,311, and is shown in the block diagram of FIG. 1. As shown in FIG. 1, an exemplary broadband wireless communication system 100 includes a plurality of cells 102. Each cell 102 contains an associated cell site 104 that primarily includes a base station 106 and an active antenna array 108. Each cell 102 provides wireless connectivity between the cell""s base station 106 and a plurality of customer premises equipment (CPE) 110 positioned at fixed customer sites 112 throughout the coverage area of the cell 102. The users of the system 100 may include both residential and business customers. Consequently, the users of the system have different and varying usage and bandwidth requirement needs. Each cell may service several hundred or more residential and business CPEs.
The broadband wireless communication system 100 of FIG. 1 provides true xe2x80x9cbandwidth-on-demandxe2x80x9d to the plurality of CPEs 110. CPEs 110 request bandwidth allocations from their respective base stations 106 based upon the type and quality of services requested by the customers served by the CPEs. Different broadband services have different bandwidth and latency requirements. The type and quality of services available to the customers are variable and selectable. The base station media access control (xe2x80x9cMACxe2x80x9d) allocates available bandwidth on a physical channel on the uplink and the downlink. Within the uplink and downlink sub-frames, the base station MAC allocates the available bandwidth between the various services depending upon the priorities and rules imposed by their quality of service (xe2x80x9cQoSxe2x80x9d). The MAC transports data between a MAC xe2x80x9clayerxe2x80x9d (information higher layers such as TCP/IP) and a xe2x80x9cphysical layerxe2x80x9d (information on the physical channel).
Due to several well known communication phenomenon occurring in the transmission link between the base stations 106 and the CPEs 112, it is well known that the transmission links or channels may be noisy and thereby produce errors during transmission. These errors are sometimes measured as Bit Error Rates (BERs) that are produced during data transmission. Depending upon the severity of these errors, communication between the base stations 106 and the CPEs 112 can be detrimentally affected. As is well known, by properly encoding data, errors introduced by noisy channels can be reduced to any desired level without sacrificing the rate of information transmission or storage. Since Shannon first demonstrated this concept in his landmark 1948 paper entitled xe2x80x9cA Mathematical Theory of Communicationxe2x80x9d, by C. E. Shannon, published in the Bell System Technical Journal, pps. 379-423 (Part I), 623-656 (Part II), in July 1948, a great deal of effort has been put forth on devising efficient coding and encoding methods for error control in a noisy communication environment. Consequently, use of error correcting coding schemes has become an integral part in the design of modem communication systems.
For example, in order to compensate for the detrimental effects produced by the noisy communication channels (or for noise that may be generated at both the sources and destinations), the data exchanged between the base stations 106 and the CPEs 112 of the system 100 of FIG. 1 may be coded using conventional combined coding and modulation designs. For example, convolutional or trellis-coded modulation (TCM)-Reed-Solomon (RS) type coders are well known in the art and can be used to code the data as it is exchanged in the system 100 of FIG. 6. Convolutional or TCM-RS concatenation coding schemes are well known in the communication art as exemplified by their description in the text entitled xe2x80x9cConvolutional Coding, Fundamentals and Applicationsxe2x80x9d, by L. H. Charles Lee, published by Artech House, Inc. in 1997, the entire text of which is hereby fully incorporated by reference for its teachings on convolutional/TCM-RS coding schemes and techniques. As is well known, in the past channel coding designs and modulation designs were treated as separate entities. Hamming distance was considered an appropriate measure for system design. TCM design offers the optimum matching between the channel encoder output code vector and the modulator using a special signal mapping technique.
As is well known, the coding gains produced by coding schemes employing convolutional or TCM coding schemes for the inner codes and RS for the outer codes (i.e., concatenating the convolutional/TCM inner codes with the RS outer codes) is relatively high in terms of the minimum Hamming distance and coding rates achieved. Disadvantageously, the high coding gains achieved by these conventional schemes come at a price in terms of complexity, cost, size, speed, data transmission delays and power. As is well known to those of skill in the art, one of the main disadvantages associated with the prior art concatenated coding schemes is that these techniques require the use of symbol xe2x80x9cinterleaversxe2x80x9d. The Convolutional/TCM-RS concatenation techniques must employ a symbol interleaver between the outer and inner codes because when the inner code decoder makes a decoding error, it usually produces a long burst of errors that affect multiple consecutive symbols of the outer decoder. Thus without a deinterleaver, the performance of the outer decoder severely degrades and the effective coding gains produced by the concatenation is lost. Furthermore, the presence of interleaver/deinterleaver distributes the error bursts over multiple outer code words thereby effectively utilizing the power of the outer codes.
In communication systems that transmit only short or variable length packets, a symbol interleaver cannot be utilized because it is impractical. In addition, the symbol interleaver required by the prior art concatenated channel coding schemes increase delays in data transmission. These increased transmission delays may be unacceptable in some applications. For example, when the system 100 of FIG. 1 is used to communicate T1-type continuous data services between the base stations and the CPEs. These type of data services often have well-controlled delivery latency requirements that may not tolerate the transmission delays introduced by the symbol interleavers utilized by the concatenated channel coding schemes of the prior art. Furthermore, the prior art concatenated channel coding schemes are relatively complex to implement and therefore suffer the power, size, and reliability disadvantages as compared with less complex implementations. As a result, prior art channel coding implementations for packet data transmission systems have typically used xe2x80x9csingle levelxe2x80x9d coding techniques such as a convolutional, TCM or block code techniques.
Block codes are typically implemented using combination logic circuits. Examples of block codes are Bose-Chaudhuri-Hocquenghem (BCH) codes, Reed-Muller (RM) codes, cyclic codes, array codes, single-error-correcting (SEC) Hamming codes, and Reed-Solomon (RS) codes. Therefore, disadvantageously, packet transmission systems, have not heretofore been able to take advantage of the benefits offered by conventional concatenation coding techniques that provide the advantage of soft-decision decoding of the inner code resulting in larger coding gain and better coding efficiencies.
Therefore, a need exists for a concatenated channel coding method and apparatus that can be easily implemented, provides acceptable coding performance, is well suited for use in small or variable size packet data transmission systems, and overcomes the disadvantages of the prior art concatenated channel coding methods and apparatuses. The present invention provides such a concatenated coding method and apparatus.
The present invention is a novel method and apparatus for efficiently coding data in a data transmission system. The inventive concatenated channel coding technique is well suited for small or variable size packet data transmission systems. The technique may also be adapted for use in a continuous mode data transmission system. The method and apparatus reduces the complexity, cost, size, power consumption typically associated with the prior art channel coding methods and apparatuses, while still achieving acceptable coding performance. The present invention advantageously performs concatenated channel coding without the necessity of a symbol interleaver. In addition, the present invention is simple to implement and thereby consumes much less space and power that do the prior art approaches. The present invention not only eliminates the need for a symbol interleaver between the outer and inner codes, but it also enjoys a drastically reduced implementation complexity of the inner code Viterbi decoder.
The inventive concatenation technique does not require a symbol interleaver (or deinterleaver on the decoder end) because when the inner code makes a decoding error, it produces only single outer code symbol errors. The present method and apparatus either corrects for the noisy received symbol using a soft decision decoding technique or it produces the erroneous symbol on the output. Consequently, the inner code can be considered as being completely matched or in other words completely dedicated to the task of assisting the outer code in working best.
The asymptotic coding gain of a code decoded with optimum decoding is given as 10log10(r dmin), where r is the code rate and dmin is the minimum Hamming distance of the code. The convolutional/TCM code employed in the conventional concatenated coding usually use an inner code having larger dmin but the code rate is usually low. The higher the dmin, the more complex the code usually is. In accordance with the present inventive coding technique, an inner code is selected to have a relatively modest dmin value. However, the coding rate is improved and better than the code used by the conventional prior art concatenated coding schemes. Another important parameter which has affect on the performance is Ndmin. This is the number of paths at distance dmin from the correct path. Low values of Ndmin are desirable for better performance. But usually, the higher the dmin, the more complex the code is to implement and it also has lower rate and higher Ndmin.
The inner code used by the present inventive coding technique has the following three advantages as compared to the prior art approaches: (1) the inner code is matched to the requirements and characteristics of the outer code (this assists the outer decoder in decoding the code in an optimum manner; (2) the inner code yields a coding technique having a relatively high coding rate thereby providing good coding gains with very modest dmin values; and (3) the inner code yields low values of Ndmin.
In the preferred embodiment of the present invention, the outer code is a (N,K) Reed-Solomon code over GF (2m). The inner code prefer ably is a (m+1, m) parity-check code. The minimum Hamming distance dmin of the inner code is 2. The overall code rate is given by the following equation, Equation 1:                               r          =                                    Km                              N                ⁡                                  (                                      m                    +                    1                                    )                                                      =                          Km                                                (                                      K                    +                    R                                    )                                ⁢                                  (                                      m                    +                    1                                    )                                                                    ;                            Equation  1:            
where R is the redundancy of the RS code, N is the length (measured in symbols) of the RS code, K is the message length (in symbols), and m is the length of the symbol in bits.
The single parity bit can be computed in parallel by an exclusive-OR of m-input bit. Alternately, it can be computed in a sequential manner with a single shift register and a single exclusive-OR gate.